Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks

摘要

Many algorithms have been proposed to predict missing links in a variety ofreal networks. These studies focus on mainly both accuracy and efficiency ofthese algorithms. However, little attention is paid to their robustness againsteither noise or irrationality of a link existing in almost all of realnetworks. In this paper, we investigate the robustness of several typicalnode-similarity-based algorithms and find that these algorithms are sensitiveto the strength of noise. Moreover, we find that it also depends on networks'structure properties, especially on network efficiency, clustering coefficientand average degree. In addition, we make an attempt to enhance the robustnessby using link weighting method to transform un-weighted network to weighted oneand then make use of weights of links to characterize their reliability. Theresult shows that proper link weighting scheme can enhance both robustness andaccuracy of these algorithms significantly in biological networks while itbrings little computational effort.